package main.回溯;

import java.util.ArrayList;
import java.util.List;

/**
 * @author tmh
 * @date 2024/9/8 15:44
 * @description
 */
public class T216组合总和III {
    List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> combinationSum3(int k, int n) {
        backTracking(k, n, 1, new ArrayList<>(), 0);
        return result;
    }

    public void backTracking(int k, int n, int beginIndex, List<Integer> list, int sum) {
        if (list.size() == k && sum == n) {
            result.add(new ArrayList<>(list));
            return;
        }
        for (int i = beginIndex; i <= 9; i++) {
            sum += i;
                list.add(i);
            backTracking(k, n, i + 1, list, sum);
            sum -= i;
            list.remove(list.size() - 1);
        }
    }
}
